import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-07
 * Time: 23:41
 */


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return getAns(1,n);
    }

    public List<TreeNode> getAns(int start,int end){
        List<TreeNode> ans=new ArrayList<>();
        //区间中没有节点
        if(start>end){
            ans.add(null);
            return ans;
        }
        //区间中只有一个节点
        if(start==end){
            TreeNode node=new TreeNode(start);
            ans.add(node);
            return ans;
        }
        //区间中有多个节点
        for(int i=start;i<=end;i++){
            //所有可能的左子树(里面存储的都是可能的左子树的根)
            List<TreeNode> left=getAns(start,i-1);
            //所有可能的右子树(里面存储的都是可能的右子树的根)
            List<TreeNode> right=getAns(i+1,end);
            //所有左子树和右子树的结合
            for(TreeNode leftNode:left){
                for(TreeNode rightNode:right){
                    //注意不能写外面,否则每次都是对同一个根进行修改,导致几棵树指向同一棵
                    TreeNode root=new TreeNode(i);
                    root.left=leftNode;
                    root.right=rightNode;
                    //里面存储的都是根节点
                    ans.add(root);
                }
            }
        }
        return ans;
    }
}
